package com.LeeCode;

/**
 * 元素和最小的山形三元组 II
 */

public class Code2909 {
    public static void main(String[] args) {
        int[] nums = {5, 4, 8, 7, 10, 2};
        System.out.println(new Code2909().minimumSum(nums));
    }

    public int minimumSum(int[] nums) {
        int ans = Integer.MAX_VALUE, n = nums.length;
        int minLeft = nums[0];

        int[] minRights = new int[n];
        minRights[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            minRights[i] = Math.min(nums[i], minRights[i + 1]);
        }


        for (int j = 1; j < n - 1; j++) {
            if (minLeft >= nums[j]) {
                minLeft = nums[j];
                continue;
            }
            if (nums[j] > minRights[j + 1]) {
                ans = Math.min(ans, minLeft + nums[j] + minRights[j + 1]);
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}
